package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 131. 分割回文串
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 * <p>
 * 回文串 是正着读和反着读都一样的字符串。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 * 示例 2：
 * <p>
 * 输入：s = "a"
 * 输出：[["a"]]
 */
public class Partition2 {

    List<List<String>> ans = new ArrayList<>();
    // dp[i][j] 表示 s.subString(i,j+1) 是否为回文串
    boolean[][] dp;
    List<String> result = new ArrayList<>();

    public static void main(String[] args) {
        String str = "aa";
        System.out.println(new Partition2().partition(str));
    }

    /**
     * 方法一. 回溯 + 动态规划（推荐）
     *
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        int n = s.length();

        // dp[i][j] 表示 s.subString(i,j+1) 是否为回文串
        dp = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        char[] arr = s.toCharArray();
        for (int length = 2; length <= arr.length; length++) {

            for (int j = 0; j < s.length(); j++) {
                int left = j;
                int right = j + length - 1;

                if (right >= s.length()) {
                    break;
                }
                if (arr[left] == arr[right]) {
                    if (right - left <= 2) {
                        dp[left][right] = true;
                    } else {
                        dp[left][right] = dp[left + 1][right - 1];
                    }
                }
            }
        }

        dfs1(s, 0);
        return ans;
    }

    /**
     * 方法二. 回溯 + 记忆化搜索（未搜索 是回文串 不是回文串）
     *
     * @param s
     * @return
     */
    public List<List<String>> partition1(String s) {
        if (s == null || s.length() == 0) {
            return ans;
        }
        return ans;
    }

    /**
     * 方法三. 回溯 + 判断
     * <p>
     * TODO 代码有点问题
     *
     * @param s
     * @return
     */
    public List<List<String>> partition2(String s) {
        if (s == null || s.length() == 0) {
            return ans;
        }
        char[] arr = s.toCharArray();
        dfs(arr, 0, new ArrayList<>());
        return ans;
    }


    public void dfs1(String s, int i) {
        if (i == s.length()) {
            ans.add(new ArrayList<String>(result));
            return;
        }
        for (int j = i; j < s.length(); ++j) {
            if (dp[i][j]) {
                result.add(s.substring(i, j + 1));
                dfs1(s, j + 1);
                result.remove(result.size() - 1);
            }
        }
    }


    public void dfs(char[] arr, int index, List<String> list) {
        String last = list.size() != 0 ? list.get(list.size() - 1) : "";
        if (index == arr.length) {
            if (isPalindrome(last)) {
                ans.add(new ArrayList<>(list));
            }
            return;
        }

        char c = arr[index];

        if (last != "" && isPalindrome(last)) {
            list.add(String.valueOf(c));
            dfs(arr, index + 1, list);
            list.remove(list.size() - 1);
        }

        String sum = last + c;
        if (list.size() == 0) {
            list.add(sum);
        } else {
            list.set(list.size() - 1, sum);
        }
        dfs(arr, index + 1, list);
    }

    public boolean isPalindrome(String a) {
        if (a == null || a.length() == 0) {
            return true;
        }
        char[] arr = a.toCharArray();
        int left = 0;
        int right = a.length() - 1;
        while (left <= right) {
            if (arr[left] != right) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
